package 中等.搜索.记忆化搜索;

import java.util.Arrays;

/**
 * 给你一个大小为 4 的整数数组 a 和一个大小 至少为 4 的整数数组 b。
 * 你需要从数组 b 中选择四个下标 i0, i1, i2, 和 i3，并满足 i0 < i1 < i2 < i3。
 * 你的得分将是 a[0] * b[i0] + a[1] * b[i1] + a[2] * b[i2] + a[3] * b[i3] 的值。
 * 返回你能够获得的 最大 得分。
 *
 * @ https://leetcode.cn/problems/maximum-multiplication-score/description/
 * @date 2024/09/15
 */
public class 最高乘法得分_3290 {

    public static void main(String[] args) {

        System.out.println(new 最高乘法得分_3290().maxScore(
                new int[]{3, 2, 5, 6},
                new int[]{2, -6, 4, -5, -3, 2, -7}
        ));

    }

    // 缓存从 a[i,end] b[j,end] 可以获取的最大得分
    private long[][] memo;

    public long maxScore(int[] a, int[] b) {
        memo = new long[a.length][b.length];
        for (long[] longs : memo) {
            Arrays.fill(longs, Long.MIN_VALUE);
        }
        dfs(a, b, 0, 0);
        return memo[0][0];
    }

    private long dfs(int[] a, int[] b, int i, int j) {
        if (i >= a.length) {
            return 0;
        }
        // 如果 4 个数还没选完，但是b已经没有数可以选了，返回一个不可能的负数
        if (j >= b.length) {
            // 防止数字溢出
            return Long.MIN_VALUE / 2;
        }
        if (memo[i][j] != Long.MIN_VALUE) {
            return memo[i][j];
        }
        return memo[i][j] = Math.max(
                (long) a[i] * b[j] + dfs(a, b, i + 1, j + 1),
                dfs(a, b, i, j + 1)
        );
    }

}
